package com.github.kezhenxu94.playground.java.sorting;

import java.util.Arrays;
import java.util.Random;
import java.util.stream.IntStream;

public class InsertionSort {
	
	public static void main(String[] args) {
		int TEST_CASES = 10;
		InsertionSort sol = new InsertionSort();
		for (int index = 0; index < TEST_CASES; index++) {
			Random random = new Random();
			IntStream stream = random.ints(20, 0, 100);
			int[] array = stream.toArray();
			int[] unsorted = Arrays.copyOf(array, array.length);
			sol.sort(unsorted);
			Arrays.sort(array);
			for (int i = 0; i < array.length; i++)
				assert array[i] == unsorted[i];
			System.out.println(String.format("Pass %d test case", index));
		}
	}
	
	/**
	 * 
	 * Base case:
	 * The subarray from [0..1) contains only one element,
	 * which is obviously sorted
	 * 
	 * Loop Invariant:
	 * The subarray from [0..i) is sorted
	 * 
	 * End condition:
	 * The subarray from [0..length), also the whole array is sorted
	 */
	public void sort(int[] array) {
		int len = array.length;
		for (int i = 1; i < len; i++) {
			int temp = array[i];
			int j = i;
			for (; j > 0 && temp < array[j - 1]; j--) {
				array[j] = array[j - 1];
			}
			array[j] = temp;
		}
	}
}
